package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/15 21:04
 * https://leetcode-cn.com/problems/water-and-jug-problem/
 */
public class Title365 {

    class State{
        int x;
        int y;

        public State(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null || obj.getClass() != getClass()) {
                return false;
            }
            State s = (State) obj;
            return this.x == s.x && this.y == s.y;
        }
    }

    public  boolean canMeasureWater(int x, int y, int z) {
        if (z == 0) {
            return false;
        }
        if (x + y < z) {
            return false;
        }
        //初始化
        State initState = new State(0, 0);
        //广度遍历使用队列
        Queue<State> queue = new LinkedList<>();
        //判断重复
        Set<State> visited = new HashSet<>();
        queue.offer(initState);
        visited.add(initState);
        while (!queue.isEmpty()) {
            State head = queue.poll();
            int curX = head.x;
            int curY = head.y;
            if (curX == z || curY == z || curX + curY == z) {
                return true;
            }
            //广度获得下一步的所有状态
            List<State> nextStates = getNextState(x, y, curX, curY);
            for (State next : nextStates) {
                if (visited.add(next)) {
                    queue.offer(next);
                }
            }
        }
        return false;
    }

    private List<State> getNextState(int x, int y, int curX, int curY) {
        //1、装满X；2、装满Y；3、清空X；4、清空Y；5、X -> Y  倒完Y满，X空  6、Y -> X  倒完X满，Y空
        List<State> list = new ArrayList<>();
        //先生成8个状态
        //1
        State s1 = new State(x, curY);
        //2
        State s2 = new State(curX, y);
        //3
        State s3 = new State(0, curY);
        //4
        State s4 = new State(curX, 0);
        //5.1
        State s5 = new State(x - (y - curY), y);
        //5.2
        State s6 = new State(0, curY + curX);
        //6.1
        State s7 = new State(x, curY - (x - curX));
        //6.2
        State s8 = new State(curY + curX, 0);
        //判断当前的curX和curY是否都要经过8个状态
        //没满才需要加水
        if (curX != x) {
            list.add(s1);
        }
        if (curY != y) {
            list.add(s2);
        }
        //有水才能倒
        if (curX != 0) {
            list.add(s3);
        }
        if (curY != 0) {
            list.add(s4);
        }
        //curX -》curY倒水，有剩余
        if (x - (y - curY) > 0) {
            list.add(s5);
        }else{
            //无剩余
            list.add(s6);
        }
        if (curY - (x - curX) > 0) {
            list.add(s7);
        }else{
            list.add(s8);
        }
        return list;
    }


    public  boolean canMeasureWater1(int x, int y, int z) {
        if (x + y < z) {
            return false;
        }
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(new int[]{x, y});
        visited.add(x + "," + y);
        while (!queue.isEmpty()) {
            int[] head = queue.poll();
            int headX = head[0];
            int headY = head[1];
            if (headX + headY == z || headX == z || headY == z) {
                return true;
            }
            //8种状态
            List<int[]> next = new ArrayList<>();
            //满
            if (headX != x) {
                next.add(new int[]{x, headY});
            }
            if (headY != y) {
                next.add(new int[]{headX, y});
            }
            //空
            if (headX != 0) {
                next.add(new int[]{0, headY});
            }
            if (headY != 0) {
                next.add(new int[]{headX, 0});
            }
            //x -> y  y满|x空
            if (headX - (y - headY) > 0) {
                next.add(new int[]{headX - (y - headY), y});
            } else {
                next.add(new int[]{0, headX + headY});
            }
            //y -> x x满|y空
            if (headY - (x - headX) > 0) {
                next.add(new int[]{x, headY - (x - headX)});
            }else{
                next.add(new int[]{headX + headY, 0});
            }
            for (int[] ints : next) {
                String temp = ints[0] + "," + ints[1];
                if (visited.add(temp)) {
                    queue.offer(ints);
                }
            }
        }
        return false;
    }


    public static void main(String[] args) {

    }
}
